// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem74.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @FilePath: \17_datac:\Users\sxjct\.leetcode\74.搜索二维矩阵.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-15 11:31:25
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-30 10:11:11
 */
/*
 * @lc app=leetcode.cn id=74 lang=cpp
 *
 * [74] 搜索二维矩阵
 */

// @lc code=start
class Solution {
public:
/*  时间复杂度 O(m+n)
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();            // 行
        int col = matrix[0].size();         // 列

        int tar_row = 0;

        for(int i = 0 ; i < row - 1 ; i++)
        {
            if(target >= matrix[i][0] && target < matrix[i + 1][0])
            {
                tar_row = i;
                break;
            }
            tar_row = i + 1;
        }

        for(int j = 0 ; j < col ; j++)
        {
            if(target == matrix[tar_row][j])
                return true;
        }
        return false;
    }
    */
// // 二分查找
//     bool searchMatrix(vector<vector<int>>& matrix, int target)
//     {
//         int row = matrix.size();
//         int col = matrix[0].size();
//         int left = 0;
//         int right = row * col - 1;
//         while(left <= right)
//         {
//             int  mid = (left+right)/2;
//             if(matrix[mid/col][mid%col] > target)
//                 right = mid - 1;
//             else if(matrix[mid/col][mid%col] < target)
//                 left = mid + 1;
//             else
//                 return true;
//         } 
//         return false;
//     }


    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();      // 行数
        int n = matrix[0].size();   // 列数
        int left = 0;
        int right = m * n - 1;
        while(left <= right)
        {
            int mid = (left + right) / 2;
            int temp = matrix[mid / n][mid % n];
            if(temp == target)
            {
                return true;
            }
            else if(temp < target)
            {
                left = mid + 1;
            }else
            {
                right = mid - 1;
            }
        }
        return false;
    }
};
// @lc code=end

